#include <bits/stdc++.h>

using namespace std;

#define N 100000

namespace Bit
{
    // 下标为1开始，注意s[N]的初始化
    // binary index tree，二叉索引树，还有一个名字叫做 Fenwick's Tree ，由发明者命名
    int n;
    int s[N];
    int lowbit(int p) { return p & (-p); }
    void init(int *nums, int size)
    {
        n = size;
        fill(begin(Bit::s), end(Bit::s), 0); // 显式初始化 Bit::s 数组为 0
        for (int i = 0; i < n; ++i)
        {
            int num = nums[i];
            s[i] += num;
            int nxt = i + (i & -i);
            if (nxt < n)
            {
                s[nxt] += s[i];
            }
        }
    }
    void init(vector<int> nums)
    {
        n = nums.size();
        fill(begin(Bit::s), end(Bit::s), 0); // 显式初始化 Bit::s 数组为 0
        for (int i = 0; i < n; ++i)
        {
            int num = nums[i];
            s[i] += num;
            int nxt = i + (i & -i);
            if (nxt < n)
            {
                s[nxt] += s[i];
            }
        }
    }
    void modify(int p, int v)
    {
        for (; p <= n; p += lowbit(p))
            s[p] += v;
    }
    int query(int p)
    {
        int ret = 0;
        for (; p > 0; p -= lowbit(p))
            ret += s[p];
        return ret;
    }
    int query(int l, int r) { return query(r) - query(l - 1); }
}